
<!DOCTYPE html>
<html lang="" class="loading">
<head>
    <meta charset="UTF-8" />
    <meta http-equiv="X-UA-Compatible" content="IE=edge,chrome=1" />
    <meta name="viewport" content="width=device-width, minimum-scale=1.0, maximum-scale=1.0, user-scalable=no">
    <title>XJUSEC2019新生赛WP - L3SLIE</title>
    <meta name="apple-mobile-web-app-capable" content="yes" />
    <meta name="apple-mobile-web-app-status-bar-style" content="black-translucent">
    <meta name="google" content="notranslate" />
    <meta name="keywords" content="L3SLIE,"> 
    <meta name="description" content="Welcome &amp; suit yourself,XJUSEC2019新生赛介绍关于XJUSEC2019新生赛的一些源码与WP
源码&amp;amp;WP源码我会放在我的仓库里，WP的话会给出本次crypto方向上的做题思路
0x01  truelove
,"> 
    <meta name="author" content="L3SLIE"> 
    <link rel="alternative" href="atom.xml" title="L3SLIE" type="application/atom+xml"> 
    <link rel="icon" href="/img/favicon.png"> 
    <link href="https://fonts.loli.net/css?family=Roboto+Mono|Rubik&display=swap" rel="stylesheet">
    
<link rel="stylesheet" href="//at.alicdn.com/t/font_1429596_nzgqgvnmkjb.css">

    
<link rel="stylesheet" href="//cdn.bootcss.com/animate.css/3.7.2/animate.min.css">

    
<link rel="stylesheet" href="//cdnjs.cloudflare.com/ajax/libs/social-share.js/1.0.16/css/share.min.css">

    
<link rel="stylesheet" href="//cdn.bootcss.com/codemirror/5.48.4/codemirror.min.css">

    
<link rel="stylesheet" href="//cdn.bootcss.com/codemirror/5.48.4/theme/dracula.css">

    
<link rel="stylesheet" href="/css/obsidian.css">

    
<link rel="stylesheet" href="/css/ball-atom.min.css">

<meta name="generator" content="Hexo 4.2.0"></head>


<body class="loading">
    <div class="loader">
        <div class="la-ball-atom la-2x">
            <div></div>
            <div></div>
            <div></div>
            <div></div>
        </div>
    </div>
    <span id="config-title" style="display:none">L3SLIE</span>
    <div id="loader"></div>
    <div id="single">
    <div class="scrollbar gradient-bg-rev"></div>
<div id="top" style="display: block;">
    <div class="bar" style="width: 0;"></div>
    <div class="navigation animated fadeIn fast delay-1s">
        <img id="home-icon" class="icon-home" src="/img/favicon.png" alt="" data-url="http://l3slie.gitee.io">
        <div id="play-icon" title="Play/Pause" class="iconfont icon-play"></div>
        <h3 class="subtitle">XJUSEC2019新生赛WP</h3>
        <div class="social">
            <!--        <div class="like-icon">-->
            <!--            <a href="javascript:;" class="likeThis active"><span class="icon-like"></span><span class="count">76</span></a>-->
            <!--        </div>-->
            <div>
                <div class="share">
                    
                        <a href="javascript:;" class="iconfont icon-share1"></a>
                        <div class="share-component-cc" data-disabled="facebook,douban,linkedin,diandian,tencent,google"></div>
                    
                </div>
            </div>
        </div>
    </div>
</div>

    <div class="section">
        <div class=article-header-wrapper>
    <div class="article-header">
        <div class="article-cover animated fadeIn" style="
            animation-delay: 600ms;
            animation-duration: 1.2s;
            background-image: 
                radial-gradient(ellipse closest-side, rgba(0, 0, 0, 0.65), #100e17),
                url(/img/cover1.jpg) ">
        </div>
        <div class="else">
            <p class="animated fadeInDown">
                
                <a href="/categories/XJUSEC"><b>「
                    </b>XJUSEC<b> 」</b></a>
                
                February 15, 2020
            </p>
            <h3 class="post-title animated fadeInDown"><a href="/2020/02/15/XJUSEC2019%E6%96%B0%E7%94%9F%E8%B5%9BWP/" title="XJUSEC2019新生赛WP" class="">XJUSEC2019新生赛WP</a>
            </h3>
            
            <p class="post-count animated fadeInDown">
                
                <span>
                    <b class="iconfont icon-text2"></b> <i>Words count</i>
                    17k
                </span>
                
                
                <span>
                    <b class="iconfont icon-timer__s"></b> <i>Reading time</i>
                    16 mins.
                </span>
                
                
                <span id="/2020/02/15/XJUSEC2019新生赛WP/" class="leancloud_visitors" data-flag-title="XJUSEC2019新生赛WP">
                    <b class="iconfont icon-read"></b> <i>Read count</i>
                    <span class="leancloud-visitors-count">100000</span>
                </span>
                
                
            </p>
            
            
            <ul class="animated fadeInDown post-tags-list" itemprop="keywords"><li class="animated fadeInDown post-tags-list-item"><a class="animated fadeInDown post-tags-list-link" href="/tags/CTF/" rel="tag">CTF</a></li><li class="animated fadeInDown post-tags-list-item"><a class="animated fadeInDown post-tags-list-link" href="/tags/WP/" rel="tag">WP</a></li></ul>
            
        </div>
    </div>
</div>

<div class="screen-gradient-after">
    <div class="screen-gradient-content">
        <div class="screen-gradient-content-inside">
            <div class="bold-underline-links screen-gradient-sponsor">
                <p>
                    <span class="animated fadeIn delay-1s"></span>
                </p>
            </div>
        </div>
    </div>
</div>

<div class="article">
    <div class='main'>
        <div class="content markdown animated fadeIn">
            <h1 id="XJUSEC2019新生赛"><a href="#XJUSEC2019新生赛" class="headerlink" title="XJUSEC2019新生赛"></a>XJUSEC2019新生赛</h1><h2 id="介绍"><a href="#介绍" class="headerlink" title="介绍"></a>介绍</h2><p>关于XJUSEC2019新生赛的一些源码与WP</p>
<h2 id="源码-amp-WP"><a href="#源码-amp-WP" class="headerlink" title="源码&amp;WP"></a>源码&amp;WP</h2><p>源码我会放在我的仓库里，WP的话会给出本次crypto方向上的做题思路</p>
<h3 id="0x01-truelove"><a href="#0x01-truelove" class="headerlink" title="0x01  truelove"></a>0x01  truelove</h3><ol>
<li><p>本题为一道娱乐题目，希望大家在做题的同时对密码学产生兴趣，并没有涉及加密原理，只是借用了火狐Mozilla的一个网页信息加密小游戏<a href="http://https://codemoji.org/" target="_blank" rel="noopener">Codemoji</a></p>
</li>
<li><p>接下来是题解，没有文件，点开是一段base64，很常见的加密，在线解base<img src="https://images.gitee.com/uploads/images/2020/0202/154857_844d277c_5231620.jpeg" alt="base"></p>
</li>
<li><p>很明显的一个网站，后面是信息提示，也就是有关解密所需KEY的提示信息，真爱的颜色，因为是一道娱乐题，<del>玩梗也是情有可原</del>（误，所以是 :green_heart: ，解出flag<img src="https://images.gitee.com/uploads/images/2020/0202/155023_da88db64_5231620.jpeg" alt="decode"></p>
<h3 id="0x02-Singer"><a href="#0x02-Singer" class="headerlink" title="0x02  Singer"></a>0x02  Singer</h3></li>
<li><p>本题是nctf的一道题，但做了一些改变，但思路完全一致。</p>
</li>
<li><p>打开是个lrc文件，直接记事本打开就行，打开后是一段歌词，仔细观察会发现中间的逻辑</p>
</li>
</ol>
<p><code>Leonard Adleman says star</code><br>Problem Makers is Problem Makers<br><code>Problem Makers says XJUSEC{</code>   </p>
<p>God takes World<br>A boy says flag<br>The boy is Bob  </p>
<p>Evil takes your mind<br>A girl says no flag<br>The girl is Alice  </p>
<p>Truths were ctf hoster violently FUCK<br><code>Bob says ar</code><br><code>Adi Shamir says rock</code></p>
<p>Love takes Alice and Bob<br>Mallory was a eavesdroppers<br>Mallory’s in hell  </p>
<p>Everything is literatures, potentially flag, Earth, description, soul<br><code>Alice says U</code><br>Reality takes God and Evil<br>God was in heaven<br>Evil is in the world<br><code>Ron Rivest says nice</code>  </p>
<p>You Want To takes Alice and Love and Anything<br>You’s Loser. Without Alice, Love or Anything  </p>
<p>Listen to your heart<br>You were Loser<br>Listen to your mind<br>Nothing was psb unfulfilled  </p>
<p>If Truths of Nothing is Everything<br>Put Ron Rivest with Adi Shamir with Leonard Adleman into RSA  </p>
<p>If Everything over Nothing is Truths<br>Put Problem Makers with Alice into Problem Makers with Bob  </p>
<p>Say Problem Makers<br>The flag is in your heart<br>The confusion is in your mind<br>Shout RSA  </p>
<p><code>Mysterious One says }</code><br>Whisper Mysterious One  </p>
<p>This is live<br>This is the truth<br>This is reality<br>This is art<br>This is CTF<br>This is NOT program<br>//flag  XJUSEC{Uarnicerockstar}  </p>
<h2 id="0x03-RSA"><a href="#0x03-RSA" class="headerlink" title="0x03  RSA"></a>0x03  RSA</h2><ol>
<li><p>求解rsa问题，首先要了解什么是RSA加密，这里我给出两个介绍RSA的文章</p>
<blockquote>
<p><a href="https://my.oschina.net/grittan/blog/3022794" target="_blank" rel="noopener">https://my.oschina.net/grittan/blog/3022794</a><br><a href="https://www.freebuf.com/articles/others-articles/166049.html" target="_blank" rel="noopener">https://www.freebuf.com/articles/others-articles/166049.html</a>  </p>
</blockquote>
</li>
<li><p>相信在看过这两篇关于RSA加密介绍的文章之后，大家对RSA加密有基本的认识。  </p>
<h3 id="babyrsa"><a href="#babyrsa" class="headerlink" title="babyrsa"></a>babyrsa</h3></li>
</ol>
<pre><code class="python">Math is cool! Use the RSA algorithm to decode the secret message, c, p, q, and e are parameters for the RSA algorithm.


p =  9648423029010515676590551740010426534945737639235739800643989352039852507298491399561035009163427050370107570733633350911691280297777160200625281665378483
q =  11874843837980297032092405848653656852760910154543380907650040190704283358909208578251063047732443992230647903887510065547947313543299303261986053486569407
e =  65537
c =  83208298995174604174773590298203639360540024871256126892889661345742403314929861939100492666605647316646576486526217457006376842280869728581726746401583705899941768214138742259689334840735633553053887641847651173776251820293087212885670180367406807406765923638973161375817392737747832762751690104423869019034

Use RSA to find the secret message</code></pre>
<p>题中已经给出了求解所需要的参数，p，q，c<br>根据rsa的加解密原理可以知道密文m = c^d mod(n)<br>所需求的就是公式中的n和d了<br>  <code>n = p*q</code><br><code>d = e-1 mod (p-1)(q-1)</code><br>那么这道题就十分简单了</p>
<pre><code class="python">import gmpy2

p= 9648423029010515676590551740010426534945737639235739800643989352039852507298491399561035009163427050370107570733633350911691280297777160200625281665378483
q= 11874843837980297032092405848653656852760910154543380907650040190704283358909208578251063047732443992230647903887510065547947313543299303261986053486569407

c = 83208298995174604174773590298203639360540024871256126892889661345742403314929861939100492666605647316646576486526217457006376842280869728581726746401583705899941768214138742259689334840735633553053887641847651173776251820293087212885670180367406807406765923638973161375817392737747832762751690104423869019034
e = 65537


d = gmpy2.invert(e,(p-1)*(q-1))

m = gmpy2.powmod(c,d,p*q)

print (m)
#m = 5577446633554466577768879988</code></pre>
<h3 id="white-give"><a href="#white-give" class="headerlink" title="white give"></a>white give</h3><pre><code class="python">n = 87924348264132406875276140514499937145050893665602592992418171647042491658461
e = 65537
c = 1323932973882505127567997561415668792873249397183695004797826407988557497789</code></pre>
<p>只给出了n，没有p和q，我们知道，p和q是大整数n的两个质因数，所以如果我们能将p和q从n中分解出来，问题就简单了<br>分解n的途径常见的有两种，一种是借助网站</p>
<blockquote>
<p><a href="http://factordb.com/" target="_blank" rel="noopener">http://factordb.com/</a></p>
</blockquote>
<p>另一种就是yafu，关于yafu的使用方法在这里就不做介绍，直接给出一篇文章</p>
<blockquote>
<p><a href="https://blog.csdn.net/qq_38063791/article/details/82947840" target="_blank" rel="noopener">https://blog.csdn.net/qq_38063791/article/details/82947840</a><br>分解n之后的做法与babyrsa类似，不过最后的结果是hex形式的需要对hex进行decode<br>脚本如下</p>
</blockquote>
<pre><code class="python">#p= 275127860351348928173285174381581152299
#q= 319576316814478949870590164193048041239

import gmpy2

p= 275127860351348928173285174381581152299
q= 319576316814478949870590164193048041239
n = 87924348264132406875276140514499937145050893665602592992418171647042491658461
c = 1323932973882505127567997561415668792873249397183695004797826407988557497789
e = 65537


d = gmpy2.invert(e,(p-1)*(q-1))

#print (d)

m = gmpy2.powmod(c,d,p*q)

#print (m)

print hex(m)[2:].decode(&#39;hex&#39;)
#flag{RSA_256_b1ts_1s_Writ3_Give}</code></pre>
<h3 id="BADRSA"><a href="#BADRSA" class="headerlink" title="BADRSA"></a>BADRSA</h3><p>本题来源于nctf的childrsa<br>但由于yafu的存在使得题目出现非预期解，此题目考察的知识点要比它看起来难上很多，原题解我会放在文末，感兴趣的话可以去看看<br>在这里只简单做一些说明，让大家熟悉一下yafu的用法。</p>
<pre><code class="python">from random import choice
from Crypto.Util.number import isPrime, sieve_base as primes
#from flag import flag


def getPrime(bits):
    while True:
        n = 2
        while n.bit_length() &lt; bits:
            n *= choice(primes)
        if isPrime(n + 1):
            return n + 1

e = 0x10001

m = int.from_bytes(flag.encode(), &#39;big&#39;)
p, q = [getPrime(2048) for _ in range(2)]
n = p * q
c = pow(m, e, n)

# n = 18593156797240319857595213690397989325525271133791312568446889915944033064100371104581731532631091503535602596625206968072471704526126177851342525418065352417467770985181453703824446545624814020088229913551168590763366199919588136847850071664562617688476529621190774851840120407058647436312506530464806016595285635383696003993673806454695717060413467152754154513144019417535456912183908101178134376622811495589460230913620523468670014115494868998771020562765366580132207086571823654068805207267678182079407136151318954715956103702385746650410960251572017154913836121903910187180085726045619388926375551835371417950821682623000024801284942564252934622066982513069808153844627952587991020946738555222228604869905329180319500884904741344175251793148508216408423855810711975532367846363239787711715995658479820222265598667056600898798739613127011506726838268704794969053178356832056364415313634801521364848664926851455419983263590758318976832638538287441294652248048314135970474560326109966170454503135840319680085501388165869698699363869575935282973343755355221069596875056759101914737700734490057013244475426116029481857089224607822710888886260861212709912726937315772190048179791994180881028699201242836562990229871501718176782600488923257
# c = 12246991997075567299333091955286124558535771125749195173423462591589599148246950536973344094697381881646070498243284004511591709851494408238456430239563188718093790844278626764266152620960525723761516246723774655578541950353158264089529439510300643359496505293058256120248042719110261394400954207742621538178576397458332260872735455432116210127719059895327941419210227101610006232743470035370738902036204650099986796091293645836805715672742051379367426351214949720255263211757929775725767927428797634547731624209359659686810461433527870721288904156665416877886649780271067791070375868453920824069906301303084454877074971598874137542612767466215920704437582555100813862848596671066251385739102728744436701245255625274142088557050389981052011799213563131697180817380536760149832811383980148304471005533360303420649405365693059920261620172024940587939854149115212644375635137458440636666665470923622968214575033240820798902963695752881087927627235477085071263835758642220223269465762162655595604457355238859189544225277027198204392960013276202883658722658835947872141708889509483326851423286849130773940575088824121527885826595551585297165117396508871896716429882836101754262475018400076172172911058852073789264898626669187248096900091196951

</code></pre>
<p>脚本如下  </p>
<pre><code class="python">import gmpy2

p = 51308963365231078823980180783163312701364591578640124732853413081668009242653641543273422167594190724551718241651039656136929815558187076682148520261848343729842506911538008029402244904426466106213994045206195486044829099911620742565757303458978079220168495663537396903552624428295943111343650722070313014422853261589496459009700711849502318089286514813530187122343076451459596577825755454359910114123985984695641426908135897672868607775230576670448429924575369916140419672246447908984584723390063778693512496129356842385118604653880078286163722831392041845536949670226969006178880514817427702855672616031799953223152447
q = 362376387628204469145269430423216951565086054878398997974719157827795227813834042397417442897515483739980090458015295807686866863247745967036097901875624568571129136298940635713503036982890741317454711334663187708069580630684509676106211476007364927949071074211673294366197423368258060221980985314778738162518411941462023209061208761828332305788032402715816093840791342483832403146518480255631024173513753665497835941124682843780600571227815518557647215798438420785146083437102412572052068194339488122442066100126626096403365800233782528237586328611544796031937811136181188887363358486926539722942031307755626350364231
N = 18593156797240319857595213690397989325525271133791312568446889915944033064100371104581731532631091503535602596625206968072471704526126177851342525418065352417467770985181453703824446545624814020088229913551168590763366199919588136847850071664562617688476529621190774851840120407058647436312506530464806016595285635383696003993673806454695717060413467152754154513144019417535456912183908101178134376622811495589460230913620523468670014115494868998771020562765366580132207086571823654068805207267678182079407136151318954715956103702385746650410960251572017154913836121903910187180085726045619388926375551835371417950821682623000024801284942564252934622066982513069808153844627952587991020946738555222228604869905329180319500884904741344175251793148508216408423855810711975532367846363239787711715995658479820222265598667056600898798739613127011506726838268704794969053178356832056364415313634801521364848664926851455419983263590758318976832638538287441294652248048314135970474560326109966170454503135840319680085501388165869698699363869575935282973343755355221069596875056759101914737700734490057013244475426116029481857089224607822710888886260861212709912726937315772190048179791994180881028699201242836562990229871501718176782600488923257
c = 12246991997075567299333091955286124558535771125749195173423462591589599148246950536973344094697381881646070498243284004511591709851494408238456430239563188718093790844278626764266152620960525723761516246723774655578541950353158264089529439510300643359496505293058256120248042719110261394400954207742621538178576397458332260872735455432116210127719059895327941419210227101610006232743470035370738902036204650099986796091293645836805715672742051379367426351214949720255263211757929775725767927428797634547731624209359659686810461433527870721288904156665416877886649780271067791070375868453920824069906301303084454877074971598874137542612767466215920704437582555100813862848596671066251385739102728744436701245255625274142088557050389981052011799213563131697180817380536760149832811383980148304471005533360303420649405365693059920261620172024940587939854149115212644375635137458440636666665470923622968214575033240820798902963695752881087927627235477085071263835758642220223269465762162655595604457355238859189544225277027198204392960013276202883658722658835947872141708889509483326851423286849130773940575088824121527885826595551585297165117396508871896716429882836101754262475018400076172172911058852073789264898626669187248096900091196951
e = 0x10001


d = gmpy2.invert(e,(p-1)*(q-1))

m = gmpy2.powmod(c,d,p*q)

print (m)

print hex(m)[2:].decode(&#39;hex&#39;)</code></pre>
<hr>
<p>下面是期望的题解</p>
<blockquote>
<p>最近在看一些整数分解的算法，其中有一个就是<code>Pollard&#39;s p-1 method。</code><br>这里输入引用文本前几天又正好在先知社区上看到了一篇Pollard’s rho algorithm的文章：<br><a href="https://xz.aliyun.com/t/6703" target="_blank" rel="noopener">https://xz.aliyun.com/t/6703</a> ，联想到一个Pollard’s p-1 method。<br>An Introduction to Mathematical Cryptography书中说到：<br>NCTF 2019 Official Writeup-小绿草信息安全实验室<br>有的时候（极少情况），RSA模数的位数越高并不意味着安全性越高。<br>存在一些比较特殊的模数，很容易被分解。<br>这个分解算法就叫做<code>Pollard&#39;s p-1 method。</code></p>
</blockquote>
<p>于是，就根据这个算法出了这一道题。</p>
<p><strong><em>Analysis</em></strong></p>
<p>这一题的关键是如何将分解n成两个5120位的大质数p, q。</p>
<p>首先，p,q由getPrime函数生成：</p>
<p>NCTF 2019 Official Writeup-小绿草信息安全实验室<br>其中，primes是Crypto.Util.number模块中定义的前10000个质数。在VScode中按F12即可跳转到定义处。</p>
<p>NCTF 2019 Official Writeup-小绿草信息安全实验室<br>可以看到，最大的质数是104729。</p>
<p>一般来说，我们寻找大质数都是随机生成一个大数，然后将其经过素性测试，能够通过的就返回。</p>
<p>但是这一题里面，并不是这样生成的。</p>
<p>我们可以看到，getPrime生成的质数，都是由前10000个质数累乘起来然后再加1生成的。</p>
<p>这就使得生成的质数p，将其减一后，其结果（也就是这个质数的欧拉函数p-1）能够被分解为许多个相对来说很小的质数。这在数学上有一个专门的术语，叫做B-smooth。很显然，p是104729-smooth的。</p>
<p>关于smooth number的定义，请参考wiki： <a href="https://en.wikipedia.org/wiki/Smooth_number" target="_blank" rel="noopener">https://en.wikipedia.org/wiki/Smooth_number</a></p>
<p>smooth有什么坏处呢？</p>
<p>我们先来看一个叫做费马小定理的东西：<br>$$<br>a^{p-1} \equiv 1 \quad (\text{mod}\ p)<br>$$<br>也就是说，指数那边每增加 $p-1$，其结果仍然不变。指数以 $p-1$ 为一个循环。</p>
<p>我们将其变形一下，<br>$$<br>a^{p-1} - 1 \equiv 0 \quad (\text{mod}\ p)<br>$$<br>模p同余0，也就是说 $a^{p-1} - 1$ 是 $p$ 的倍数。</p>
<p>将同余式改写为等式，<br>$$<br>a^{t \times (p-1)} - 1 = k\times p<br>$$</p>
<p>其中 $t, k$ 是两个整数。</p>
<p>如果指数$exp$是 $p-1$ 的倍数，那么$a^{exp} - 1 $就会是 $p$ 的倍数。</p>
<p>上面的$p$均指某一个质数，而非N = pq中的p</p>
<p>这里很关键。</p>
<p>如果我们能够找到一个指数$L$，使得对于某一个底数$a$，$a^{L} - 1$ 是p的倍数，但不是q的倍数。</p>
<p>这时，我们只要去计算<br>$$<br>gcd(a^{L}-1, N)<br>$$<br>得到的结果，必定是p。也就是说，我们成功地分解了N。</p>
<p>那么，怎么去找到这个$L$呢？</p>
<p>Pollard的厉害之处就在于此，他发现，如果p-1正好是一些很小的质数的乘积，那么p-1就能整除$n!$，其中$n$是一个不太大的数。</p>
<p>为什么呢？说下我自己的理解。</p>
<p>假设p-1是p1, p2, …, pk这些质数的乘积，其中最大的质数是pk。那么，很显然pk!=1·2·…·pk肯定包括了p1, p2, …, pk这些质数的乘积，pk!肯定是p-1的倍数。</p>
<p>也就是说，$n &gt; pk$ 的时候，$n!$很大概率上就能被p-1整除。（考虑到p1, p2, …, pk中可能有重复的情况）</p>
<p>这导致了Pollard’ p-1 method：</p>
<p>对于每一个$n = 2, 3, 4, …$，我们任意选择一个底数$a$（事实上，我们可以简单地选择为2），并计算<br>$$<br>gcd(a^{n!-1}, N)<br>$$<br>如果结果落在1和$N$中间，那么我们就成功了。</p>
<p>NCTF 2019 Official Writeup-小绿草信息安全实验室<br>实际操作中，这个算法有很多可以优化的地方。</p>
<p>例如，我们并不需要算出$a^{n!-1}$的确切值，当$n&gt;100$时，$n!$本身就已经很大了，整体结果肯定巨大无比。我们每一次只需要算出$a^{n!-1}\ \text{mod}\ N$的值即可，可以将运算结果限制在模$N$的范围内。</p>
<p>这一题，实际上我们已经知道了最大的质数为104729，我们大概只需要算到$n = 104729$就可以了（不考虑p-1的构成中有几个重复的比较大的质数）。</p>
<p>并不需要每一个$n$都去算一遍$gcd(a^{n!-1}, N)$，每隔一个恰当的间隔去算就可以了。</p>
<p>Exploit</p>
<p>先自己照着算法流程实现一下Pollard’s p-1 method：</p>
<pre><code class="python">from Crypto.Util.number import *

def Pollard_p_1(N):
    a = 2
    while True:
        f = a
        # precompute
        for n in range(1, 80000):
            f = pow(f, n, N)
        for n in range(80000, 104729+1):
            f = pow(f, n, N)
            if n % 15 == 0:
                d = GCD(f-1, N)
                if 1 &lt; d &lt; N:
                    return d
        print(a)
        a += 1COPY</code></pre>
<p>然后就直接去分解这个10000+位的N。</p>
<p><code>n = 1592519204764870135...</code></p>
<p><code>print( Pollard_p_1(n) )</code></p>
<p>大概<em>跑个十几分钟</em>（由于这个N太大了，十万次左右的快速幂还是需要点时间的），能分解出来：</p>
<p>NCTF 2019 Official Writeup-小绿草信息安全实验室<br>后面就是正常的RSA解密了。</p>
<pre><code class="python">from Crypto.Util.number import *

n = 1592519204764870135...
c = 5744608257563538066...
p = 5075332621067110585...
q = n // p
assert(p*q == n)

d = inverse(0x10001, (p-1)*(q-1))

m = pow(c, d, n)
print(long_to_bytes(m))
# b&#39;NCTF{Th3r3_ar3_1ns3cure_RSA_m0duli_7hat_at_f1rst_gl4nce_appe4r_t0_be_s3cur3}&#39;</code></pre>
<p><strong><em>Summary</em></strong></p>
<p>出这一道题的目的，还是希望能让大家去深入了解某些算法背后的原理。</p>
<blockquote>
<p>不过看大家好像都是用yafu直接分解的。。。。而且还挺快的。</p>
</blockquote>

            <!--[if lt IE 9]><script>document.createElement('audio');</script><![endif]-->
            <audio id="audio" loop="1" preload="auto" controls="controls"
                data-autoplay="false">
                <source type="audio/mpeg" src="">
            </audio>
            
            <ul id="audio-list" style="display:none">
                
                
                <li title='0' data-url='/statics/i saw you in a dream.mp3'></li>
                
                    
            </ul>
            
            
            
            <div id="vcomments"></div>
            
        </div>
        <div class="sidebar">
            <div class="box animated fadeInRight">
                <div class="subbox">
                    <img src="/img/avatar.jpg" height=300 width=300></img>
                    <p>L3SLIE</p>
                    <span>Life Long & Pwn</span>
                    <dl>
                        <dd><a href="https://github.com/13slie" target="_blank"><span
                                    class=" iconfont icon-github"></span></a></dd>
                        <dd><a href="" target="_blank"><span
                                    class=" iconfont icon-twitter"></span></a></dd>
                        <dd><a href="https://stackexchange.com/users/17805607/l3slie" target="_blank"><span
                                    class=" iconfont icon-stack-overflow"></span></a></dd>
                    </dl>
                </div>
                <ul>
                    <li><a href="/">46 <p>Articles</p></a></li>
                    <li><a href="/categories">13 <p>Categories</p></a></li>
                    <li><a href="/tags">20 <p>Tags</p></a></li>
                    <br><span><b><p>友链博客</p></b></span><br>
                    <span><u><p><a href="http://rdd.xjusec.club/" target="_blank">Rdd</a></p></u></span>
                    <span><u><p><a href="http://www.xjusec.club/" target="_blank">XJUSEC</a></p></u></span>
                    <span><u><p><a href="http://www.r1ght0us.xyz/" target="_blank">r1ght0us</a></p></u></span>
                </ul>
            </div>
            
            
            
            <div class="box sticky animated fadeInRight faster">
                <div id="toc" class="subbox">
                    <h4>Contents</h4>
                    <ol class="toc"><li class="toc-item toc-level-1"><a class="toc-link" href="#XJUSEC2019新生赛"><span class="toc-number">1.</span> <span class="toc-text">XJUSEC2019新生赛</span></a><ol class="toc-child"><li class="toc-item toc-level-2"><a class="toc-link" href="#介绍"><span class="toc-number">1.1.</span> <span class="toc-text">介绍</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#源码-amp-WP"><span class="toc-number">1.2.</span> <span class="toc-text">源码&amp;WP</span></a><ol class="toc-child"><li class="toc-item toc-level-3"><a class="toc-link" href="#0x01-truelove"><span class="toc-number">1.2.1.</span> <span class="toc-text">0x01  truelove</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#0x02-Singer"><span class="toc-number">1.2.2.</span> <span class="toc-text">0x02  Singer</span></a></li></ol></li><li class="toc-item toc-level-2"><a class="toc-link" href="#0x03-RSA"><span class="toc-number">1.3.</span> <span class="toc-text">0x03  RSA</span></a><ol class="toc-child"><li class="toc-item toc-level-3"><a class="toc-link" href="#babyrsa"><span class="toc-number">1.3.1.</span> <span class="toc-text">babyrsa</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#white-give"><span class="toc-number">1.3.2.</span> <span class="toc-text">white give</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#BADRSA"><span class="toc-number">1.3.3.</span> <span class="toc-text">BADRSA</span></a></li></ol></li></ol></li></ol>
                </div>
            </div>
            
            
        </div>
    </div>
</div>

    </div>
</div>
    <div id="back-to-top" class="animated fadeIn faster">
        <div class="flow"></div>
        <span class="percentage animated fadeIn faster">0%</span>
        <span class="iconfont icon-top02 animated fadeIn faster"></span>
    </div>
</body>
<footer>
    <p class="copyright" id="copyright">
		<span id="timeDate">载入天数...</span><span id="times">载入时分秒...</span>
		<script>
		var now = new Date(); 
		function createtime() { 
			var grt= new Date("01/10/2020 00:00:00");//在此处修改你的建站时间
			now.setTime(now.getTime()+250); 
			days = (now - grt ) / 1000 / 60 / 60 / 24; dnum = Math.floor(days); 
			hours = (now - grt ) / 1000 / 60 / 60 - (24 * dnum); hnum = Math.floor(hours); 
			if(String(hnum).length ==1 ){hnum = "0" + hnum;} minutes = (now - grt ) / 1000 /60 - (24 * 60 * dnum) - (60 * hnum); 
			mnum = Math.floor(minutes); if(String(mnum).length ==1 ){mnum = "0" + mnum;} 
			seconds = (now - grt ) / 1000 - (24 * 60 * 60 * dnum) - (60 * 60 * hnum) - (60 * mnum); 
			snum = Math.round(seconds); if(String(snum).length ==1 ){snum = "0" + snum;} 
			document.getElementById("timeDate").innerHTML = "本站已安全运行 "+dnum+" 天 "; 
			document.getElementById("times").innerHTML = hnum + " 小时 " + mnum + " 分 " + snum + " 秒"; 
		} 
		setInterval("createtime()",250);
		</script>
        &copy; 2020
        <span class="gradient-text">
            L3SLIE
        </span>❤
        Powered by <a href="http://hexo.io/" title="Hexo" target="_blank" rel="noopener">Hexo</a>
        Theme
        <span class="gradient-text">
            <a href="https://github.com/TriDiamond/hexo-theme-obsidian" title="Obsidian" target="_blank" rel="noopener">Obsidian</a>
        </span>
        <small><a href="https://github.com/TriDiamond/hexo-theme-obsidian/blob/master/CHANGELOG.md" title="v1.4.3" target="_blank" rel="noopener">v1.4.3</a></small>
    </p>
</footer>

<script type="text/javascript" src="https://cdn.bootcss.com/mathjax/2.7.6/MathJax.js?config=TeX-AMS-MML_HTMLorMML">
</script>
<script>
  MathJax.Hub.Config({
    "HTML-CSS": {
      preferredFont: "TeX",
      availableFonts: ["STIX", "TeX"],
      linebreaks: {
        automatic: true
      },
      EqnChunk: (MathJax.Hub.Browser.isMobile ? 10 : 50)
    },
    tex2jax: {
      inlineMath: [
        ["$", "$"],
        ["\\(", "\\)"]
      ],
      processEscapes: true,
      ignoreClass: "tex2jax_ignore|dno",
      skipTags: ['script', 'noscript', 'style', 'textarea', 'pre', 'code']
    },
    TeX: {
      noUndefined: {
        attributes: {
          mathcolor: "red",
          mathbackground: "#FFEEEE",
          mathsize: "90%"
        }
      },
      Macros: {
        href: "{}"
      }
    },
    messageStyle: "none"
  });
</script>
<script>
  function initialMathJax() {
    MathJax.Hub.Queue(function () {
      var all = MathJax.Hub.getAllJax(),
        i;
      // console.log(all);
      for (i = 0; i < all.length; i += 1) {
        console.log(all[i].SourceElement().parentNode)
        all[i].SourceElement().parentNode.className += ' has-jax';
      }
    });
  }

  function reprocessMathJax() {
    if (typeof MathJax !== 'undefined') {
      MathJax.Hub.Queue(["Typeset", MathJax.Hub]);
    }
  }
</script>




<script src="//cdnjs.cloudflare.com/ajax/libs/jquery/3.4.1/jquery.min.js"></script>
<script src="/js/plugin.js"></script>
<script src="/js/obsidian.js"></script>
<script src="/js/jquery.truncate.js"></script>
<script src="/js/search.js"></script>


<script src="//cdn.bootcss.com/typed.js/2.0.10/typed.min.js"></script>


<script src="//cdn.bootcss.com/blueimp-md5/2.12.0/js/md5.min.js"></script>


<script src="//cdnjs.cloudflare.com/ajax/libs/social-share.js/1.0.16/js/social-share.min.js"></script>


<script src="https://cdn.bootcss.com/codemirror/5.48.4/codemirror.min.js"></script>

    
<script src="//cdn.bootcss.com/codemirror/5.48.4/mode/javascript/javascript.min.js"></script>


    
<script src="//cdn.bootcss.com/codemirror/5.48.4/mode/css/css.min.js"></script>


    
<script src="//cdn.bootcss.com/codemirror/5.48.4/mode/xml/xml.min.js"></script>


    
<script src="//cdn.bootcss.com/codemirror/5.48.4/mode/htmlmixed/htmlmixed.min.js"></script>


    
<script src="//cdn.bootcss.com/codemirror/5.48.4/mode/clike/clike.min.js"></script>


    
<script src="//cdn.bootcss.com/codemirror/5.48.4/mode/php/php.min.js"></script>


    
<script src="//cdn.bootcss.com/codemirror/5.48.4/mode/shell/shell.min.js"></script>


    
<script src="//cdn.bootcss.com/codemirror/5.48.4/mode/python/python.min.js"></script>




    
<script src="/js/busuanzi.min.js"></script>

    <script>
        $(document).ready(function () {
            if ($('span[id^="busuanzi_"]').length) {
                initialBusuanzi();
            }
        });
    </script>



<link rel="stylesheet" href="//cdn.bootcss.com/photoswipe/4.1.3/photoswipe.min.css">
<link rel="stylesheet" href="//cdn.bootcss.com/photoswipe/4.1.3/default-skin/default-skin.min.css">


<script src="//cdn.bootcss.com/photoswipe/4.1.3/photoswipe.min.js"></script>
<script src="//cdn.bootcss.com/photoswipe/4.1.3/photoswipe-ui-default.min.js"></script>


<!-- Root element of PhotoSwipe. Must have class pswp. -->
<div class="pswp" tabindex="-1" role="dialog" aria-hidden="true">
    <!-- Background of PhotoSwipe. 
         It's a separate element as animating opacity is faster than rgba(). -->
    <div class="pswp__bg"></div>
    <!-- Slides wrapper with overflow:hidden. -->
    <div class="pswp__scroll-wrap">
        <!-- Container that holds slides. 
            PhotoSwipe keeps only 3 of them in the DOM to save memory.
            Don't modify these 3 pswp__item elements, data is added later on. -->
        <div class="pswp__container">
            <div class="pswp__item"></div>
            <div class="pswp__item"></div>
            <div class="pswp__item"></div>
        </div>
        <!-- Default (PhotoSwipeUI_Default) interface on top of sliding area. Can be changed. -->
        <div class="pswp__ui pswp__ui--hidden">
            <div class="pswp__top-bar">
                <!--  Controls are self-explanatory. Order can be changed. -->
                <div class="pswp__counter"></div>
                <button class="pswp__button pswp__button--close" title="Close (Esc)"></button>
                <button class="pswp__button pswp__button--share" title="Share"></button>
                <button class="pswp__button pswp__button--fs" title="Toggle fullscreen"></button>
                <button class="pswp__button pswp__button--zoom" title="Zoom in/out"></button>
                <!-- Preloader demo http://codepen.io/dimsemenov/pen/yyBWoR -->
                <!-- element will get class pswp__preloader--active when preloader is running -->
                <div class="pswp__preloader">
                    <div class="pswp__preloader__icn">
                      <div class="pswp__preloader__cut">
                        <div class="pswp__preloader__donut"></div>
                      </div>
                    </div>
                </div>
            </div>
            <div class="pswp__share-modal pswp__share-modal--hidden pswp__single-tap">
                <div class="pswp__share-tooltip"></div> 
            </div>
            <button class="pswp__button pswp__button--arrow--left" title="Previous (arrow left)">
            </button>
            <button class="pswp__button pswp__button--arrow--right" title="Next (arrow right)">
            </button>
            <div class="pswp__caption">
                <div class="pswp__caption__center"></div>
            </div>
        </div>
    </div>
</div>







<script>
    function initialTyped () {
        var typedTextEl = $('.typed-text');
        if (typedTextEl && typedTextEl.length > 0) {
            var typed = new Typed('.typed-text', {
                strings: ["Life Long &amp; Pwn", "生命不息，破解不止"],
                typeSpeed: 90,
                loop: true,
                loopCount: Infinity,
                backSpeed: 20,
            });
        }
    }

    if ($('.article-header') && $('.article-header').length) {
        $(document).ready(function () {
            initialTyped();
        });
    }
</script>


    
<script src="//unpkg.com/valine/dist/Valine.min.js"></script>

    <script>

        var valine = new Valine();

        function initValine(path) {
            if (!path) path = window.location.pathname;
            let language = '';
            if (!language) {
                language = 'en';
            } else {
                language = language.toLowerCase();
            }
            valine.init({
                el: '#vcomments',
                appId: 'GnPlbHQ9xAWEoCDC8rR3zALj-gzGzoHsz',
                appKey: 'Nygd2awSxr9ioTDtvbH6hE0l',
                notify: 'false',
                verify: 'false',
                avatar: 'mm',
                placeholder: 'feel free to comment~',
                visitor: 'true',
                path: path,
                lang: language
            });
        }

        $(document).ready(function () {
            initValine();
        });
    </script>



</html>
<!-- 页面点击小红心 -->
<script type="text/javascript" src="/js/love.js"></script>
<!-- 烟火效果 -->
<canvas class="fireworks" style="position: fixed;left: 0;top: 0;z-index: 1; pointer-events: none;" ></canvas> 
<script type="text/javascript" src="//cdn.bootcss.com/animejs/2.2.0/anime.min.js"></script> 
<script type="text/javascript" src="/js/fireworks.js"></script>
<!--自定义标题-->
<script type="text/javascript" src="\js\title.js"></script>
